package com.code.test.first.hash;

import java.util.ArrayList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/1002.%E6%9F%A5%E6%89%BE%E5%B8%B8%E7%94%A8%E5%AD%97%E7%AC%A6.md
 * <p>
 * 给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。
 * <p>
 * 示例 1：
 * <p>
 * 输入：words = ["bella","label","roller"] 输出：["e","l","l"]
 * <p>
 * 示例 2：
 * <p>
 * 输入：words = ["cool","lock","cook"] 输出：["c","o"]
 */
public class Code1002 {

    public static void main(String[] args) {
        String[] input = {"bella", "label", "roller"};
        System.out.println(commonChars(input));
    }

    public static List<String> commonChars(String[] input) {

        List<String> result = new ArrayList<>();

        if (input.length == 0) return result;

        int[] hash = new int[26];
        //初始化
        for (int i = 0; i < input[0].length(); i++) {
            hash[input[0].charAt(i) - 'a']++;
        }
        //统计除第一个字符串字符的出现频率
        for (int i = 1; i < input.length; i++) {
            int[] otherHash = new int[26];
            for (int j = 0; j < input[i].length(); j++) {
                otherHash[input[i].charAt(j) - 'a']++;
            }
            //更新hash，保证hash统计里26个字符在所有字符串里出现的最小次数
            //如果第二个字符中某个字符出现的个数小于第一个字符串，那么每个字符最大公共个数就应该是最小的那个
            for (int k = 0; k < 26; k++) {
                hash[k] = Math.min(hash[k], otherHash[k]);
            }
        }

        for (int i = 0; i < 26; i++) {
            //这里是while，因为同一个字符可能出现多次
            /**
             * 先判断hash[i]是否有该字符，再判断有没有多个，把多个连起来放到结果集
             */
            while (hash[i] != 0) {
                char c = (char) (i + 'a');
                result.add(String.valueOf(c));
                hash[i]--;
            }
        }
        return result;
    }


}
